1. The Field of the Invention
The present invention generally relates to preventing denial of service attacks over data transport protocols. More specifically, the present invention provides for applying a cryptographically secure hash to packets from unverified remote entities, with the purpose of preventing denial of service attacks on lookup tables used to store state information for one or more remote entities, while maintaining the performance of a local server for packets from verified remote entities.
2. Background and Related Art
Computer systems and related technology effect many aspects of society. Indeed, the computer systems ability to process information has transformed the way we live and work. Computer systems now commonly perform a host of tasks (e.g., word processing, scheduling, database management, etc.) that prior to the advent of the computer system were performed manually. Increasingly, separate computer systems have been coupled to one another to form computer networks over which the computer systems can communicate electronically to share data. As a result, many of the tasks performed at a computer system (e.g., accessing electronic mail and web browsing) include electronic communication with one or more other computer systems via a computer network (e.g., the Internet).
Often, electronic communication on a computer network includes a client computer system (hereinafter referred to as a “remote client” or “remote entity”) requesting access to a service (e.g., electronic mail or a web page) at a server computer system (hereinafter referred to as a “local server”). Before granting the client or entity access to the service, the server may issue a challenge to the client requiring the client to prove it's identity to the server. A challenge may be a relatively simple one, for example, challenging a user at the client to enter user-name and password. On the other hand, a challenge may be more complex, such as challenging the client to correctly perform a complex handshake sequence.
One reliable data transport protocol that uses a handshake sequence when challenging a client is known as transmission control protocol (TCP). TCP is used for establishing reliable bidirectional streams, like those used for remote terminal connections (established with telnet or login utilities). TCP is also used for transferring large amounts of data, for example, with file transfer protocol (FTP) or by connecting to a Web server.
Unlike most other parts of the Internet Protocol suite (such as Internet Control Message Protocol (ICMP) or User Datagram Protocol (UDP)), TCP establishes a connection between the local and remote site. As mentioned above, these TCP connections are generally reliable and secure, and therefore a challenge to the client in the form of a handshake is used to prevent attackers from gaining access to the connection.
FIG. 1 illustrates a typical TCP three way handshake, i.e., the exchange of three messages, used to establish a connection between a remote client 105 and a local server 110. The remote client 105 sends an initial synchronization (SYN) segment, which includes an initial sequence number (ISN), shown here as ISNC. The local server 110 responds with a SYN 125 comprising its own ISN (shown here as ISNS), and an acknowledgement (ACK) 120. This ACK 120 includes the ISNC received from the remote client 105 plus one, which among other things lets the remote client 105 know that the local server 110 received it's SYN.
Similar to the local server 110, when the client system 105 receives the SYN 125 and ACK 120 packet, it must send back its own ACK message 130, which will include the local server's 110 ISNS plus one. The ISNS generated from the remote client 105 and the local server 110 are used not only to assign sequence numbers to data packets exchanged between the two, but also as a way to ensure that each received the appropriate package and that each is communicating with the entity they initially believed to be communicating.
To protect against spoofing attacks (i.e., those attacks where an attacker floods the local server with data packets from a spoofed address by knowing or predicting the sequence numbers used), many operating systems use random number generators to choose TCP ISNs. Typically, the ISNs are generated using data unique to the connection, e.g., connection identifier or key information (usually some combination of source/destination routing address and port). This information, or at least a portion thereof, may be hashed using secure hash function in order to generate an ISN intended to be unpredictable.
For each connection requested, or established, TCP also creates and maintains a data structure called a transmission control block (TCB), which includes, e.g., state variables for the connection. For example, when a SYN segment is received for requesting a connection, a TCB may be created that may include information about the ISN generated, expected round trip time of data packets, etc. Further, once a connection is established, the TCB continues maintaining information about, e.g., a connection state, its associated local process, feedback parameters about the connection's transmission properties, expected sequence numbers, etc.
TCBs are maintained on a per-connection basis and are stored in a hash table that allows for efficient lookups. FIG. 2 illustrates an example of a typical TCB lookup table 200 used for storing and maintaining state information for each connection. When a remote client requests a connection, i.e., sends a SYN, a TCB 215 is generated and indexed within TCB lookup table 200. Typically, the index 205 is determined based on a simple hash 220 of information unique to the connection, e.g., the connection key 210. When a data segment subsequently comes in from the network, one of the first tasks performed is to find the matching TCB 215 for that segment. Accordingly, the information unique to the connection 210 is again hashed 220, yielding the appropriate index 205 containing the TCB 215 and the corresponding state information.
Because TCBs are maintained on a per-connection basis, as the number of connections maintained increases, the number of maintained TCBs also increases. Recently, hackers are attacking this lookup methodology by making TCP hash all (or most) of the TCBs it creates to the same hash index. This makes each lookup take much longer than usual because what should be a hashed lookup devolves into a sequential one. This attack is possible because the hash function currently used by the TCP is simple and insecure. That is, the attackers are able to determine the hash function used to index TCBs, and similar to the spoofing problem mentioned above for ISNs, attackers can flood the local server with connection identifiers that hash TCBs into one index. Due to the prolonged lookups, any subsequent legitimate remote entities that attempt to connect to the local server are likely to experience poor response times or will be unable to connect because submitted connection requests will time out.
One solution to this DoS attack is to use a secure hash for the lookup tables. For example, similar to the secure hash function used to generate the ISNs, a cryptographically secure hash can be used to produce indices that cannot be easily predicted. The problem with this solution, however, is that securely hashing connection identification information for each packet of data received by the local server consumes considerable CPU cycles, thereby reducing the overall performance of the local server system. Accordingly, there exists a need for preventing DoS attacks on lookup tables, while maintaining the performance of the local server.